﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

public class Variations
{
    public static int n;
    public static int k;
    public static List<int> elements = new List<int>();
    public static int digitsOfN;
    public static List<int> baseCombination = new List<int>();
    public static List<int> permutation = new List<int>();

    public static void Main()
    {
        do
        {
            DataInput();
            System.Threading.Thread.Sleep(2000);
            AllVariations(elements, k);
            Console.Write("\nPress any key to see other variations...");
            Console.ReadKey();
        } while (true);
    }

    public static void DataInput()
    {
        BigInteger variations;

        do
        {
            Console.Clear();
            Console.Write("\nVariations\n\nN = ");
            if ((int.TryParse(Console.ReadLine(), out n) && (0 < n)))
                break;
        } while (true);

        do
        {
            Console.Clear();
            Console.Write("\nVariations\n\nN = {0}\n", n);
            Console.Write("\nK = ");
            if ((int.TryParse(Console.ReadLine(), out k) && (0 < k) && (k <= n)))
                break;
        } while (true);

        Console.WriteLine();

        elements.Clear();
        for (int i = 1; i <= n; i++)
            elements.Add(i);

        digitsOfN = Digits(n);

        variations = n;
        for (int i = n - 1; i >= n - k + 1; i--)
            variations *= i;

        Console.WriteLine("All variations are {0}\n", variations);
    }

    static void AllVariations(List<int> elements, int k)
    {
        int members = elements.Count;
        int ones = 0;
        StringBuilder combination = new StringBuilder(members);
        for (int i = 0; i < members; i++)
            combination.Append("0");

        do
        {
            if (ones == k)
            {
                baseCombination.Clear();

                for (int j = members - 1; j >= 0; j--)
                    if (combination[j] == '1')
                        baseCombination.Add(n - elements[j] + 1);

                AllPermutations(baseCombination);

            }

            if (combination[members - 1] == '0')
            {
                combination[members - 1] = '1';
                ones++;
            }
            else if (ones == members)
                break;
            else
            {
                combination[members - 1] = '0';
                for (int i = members - 2; i >= 0; i--)
                {
                    if (combination[i] == '0')
                    {
                        combination[i] = '1';
                        break;
                    }
                    else
                    {
                        combination[i] = '0';
                        ones--;
                    }
                }
            }
        } while (ones <= members);
    }

    public static int Digits(int p)
    {
        int m = p;
        int digits = 0;

        while (m > 0)
        {
            digits++;
            m /= 10;
        }

        return digits;
    }

    private static void AllPermutations(List<int> baseCombination)
    {
        int els = baseCombination.Count;
        BigInteger allPermutations = els;
        for (int i = els - 1; i > 1; i--)
            allPermutations *= i;

        BigInteger kEmptyPosition;
        int rightEmptyPosition;
        BigInteger structure;

        permutation.Clear();
        for (int i = 0; i < els; i++)
            permutation.Add(i + 1);

        for (long row = 0; row < allPermutations; row++)
        {
            for (int i = 0; i < els; i++)
                permutation[i] = 0;

            for (int element = els; element > 0; element--)
            {
                structure = allPermutations;
                for (int i = els; i >= element; i--)
                    structure /= i;

                kEmptyPosition = (row / structure) % element;

                rightEmptyPosition = -1;

                for (int i = 0; i < els; i++)
                {
                    if (permutation[i] == 0)
                    {
                        rightEmptyPosition++;
                        if (rightEmptyPosition == kEmptyPosition)
                        {
                            permutation[i] = els - element + 1;
                            break;
                        }
                    }
                }
            }

            Console.Write("{0}{1}", new string(' ', (digitsOfN - Digits(baseCombination[permutation[0] - 1]))), baseCombination[permutation[0] - 1]);
            for (int i = 1; i < els; i++)
                Console.Write(" {0}{1}", new string(' ', (digitsOfN - Digits(baseCombination[permutation[i] - 1]))), baseCombination[permutation[i] - 1]);

            Console.WriteLine();
        }
    }
}